// https://www.lintcode.com/problem/shortest-unsorted-continuous-subarray/

public class Solution {
    /**
     * @param nums: an array
     * @return: the shortest subarray's length
     */
    public int findUnsortedSubarray(int[] nums) {
        // Write your code here
        // 1. 找到最右边的比之前max小的元素
        // 2. 找到最左边的比之后min大的元素
        int nlen = nums.length - 1;
        int max = nums[0], min = nums[nlen];
        int l = -1, r = -2;
        for (int i = 1; i < nlen; ++i) {
            max = Math.max(max, nums[i]);
            min = Math.min(min, nums[nlen - i - 1]);
            if (max != nums[i]) {
                r = i;
            }
            if (min != nums[nlen - i - 1]) {
                l = nlen - i - 1;
            }
        }
        return r - l + 1;
    }
}